% !TeX spellcheck = <none>
\documentclass{beamer}

\usepackage{pgf,pgfpages}
\usepackage{graphicx}
%\usepackage{units}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\mode<presentation>
{
  \usetheme{ift}
  \setbeamercovered{transparent}
  \setbeamertemplate{items}[square]
  \setbeamertemplate{caption}[numbered]
}

\usefonttheme[onlymath]{serif}
\setbeamerfont{frametitle}{size=\LARGE,series=\bfseries}

\definecolor{uibred}{RGB}{170, 0, 0}
\definecolor{uibblue}{RGB}{0, 84, 115}
\definecolor{uibgreen}{RGB}{119, 175, 0}
%\definecolor{uibgreen}{RGB}{50, 105, 0}
\definecolor{uiborange}{RGB}{217, 89, 0}


\beamertemplatenavigationsymbolsempty


%\include{macros}

%\includeonlyframes{current}


\defbeamertemplate{enumerate item}{mycircle}
{
  %\usebeamerfont*{item projected}%
  %\usebeamercolor[bg]{item projected}%
  \begin{pgfpicture}{0ex}{0ex}{1.5ex}{0ex}
	%\pgfcircle[fill]{\pgfpoint{0pt}{.75ex}}{1.25ex}
    \pgfbox[center,base]{\color{uibblue}\insertenumlabel.}
  \end{pgfpicture}%
}
[action]
{\setbeamerfont{item projected}{size=\scriptsize}}
\setbeamertemplate{enumerate item}[mycircle]

\lstset{
 	language=C,
% 	captionpos=b,
 	tabsize=3,
 	frame=lines,
 	keywordstyle=\color{blue},
 	commentstyle=\color{gray},
 	stringstyle=\color{green},
	extendedchars=true,
% 	numbers=left,
 	numberstyle=\tiny,
 	numbersep=5pt,
 	breaklines=true,
 	showstringspaces=false,
 	basicstyle=\footnotesize\ttfamily,
 	emph={label},
 	inputencoding=utf8,
 	extendedchars=true,
  literate=%
  {é}{{\'{e}}}1
  {è}{{\`{e}}}1
  {ê}{{\^{e}}}1
  {ë}{{\¨{e}}}1
  {û}{{\^{u}}}1
  {ù}{{\`{u}}}1
  {â}{{\^{a}}}1
  {à}{{\`{a}}}1
  {î}{{\^{i}}}1
  {ç}{{\c{c}}}1
  {Ç}{{\c{C}}}1
  {É}{{\'{E}}}1
  {Ê}{{\^{E}}}1
  {À}{{\`{A}}}1
  {Â}{{\^{A}}}1
  {Î}{{\^{I}}}1
    }



\title{ \textbf{Domain-based consitency techniques}}
\author{
\vspace{0.2cm}
\vspace{0.2cm}
\vspace{0.2cm}
Student  : KHONG Minh Thanh\\
Professor: Yves Deville}

\institute{
P17, Institut de la Francophonie pour l'Informatique \\
\& beCool Constraints Group, ICTEAM/INGI, UCL
}
\date{}

\AtBeginSection[]
{
\addtocounter{framenumber}{-1}
\begin{frame}<beamer>{Table of Contents}
\tableofcontents[currentsection,currentsubsection, 
    hideothersubsections, 
    sectionstyle=show/shaded,
]
\end{frame}
}

\begin{document}
\maketitle
%
% Set the background for the rest of the slides.
% Insert infoline at the end 
%
\setbeamertemplate{background}
 {\includegraphics[width=\paperwidth,height=\paperheight]{images/slide_bg}}
\setbeamertemplate{footline}[ifttheme]

\begin{frame}
  \frametitle{Plan}
  \addtocounter{framenumber}{-1}
  \tableofcontents
\end{frame}

%--------------------------------------------------------------------
%                          Introduction
%--------------------------------------------------------------------
\section{Definitions}
\begin{frame}{Definitions}
\textbf{Constraint Satifaction Problem (CSP)} $(X, D(X), C)$ is a composed of:
\begin{itemize}
\item a set $X = x_1,\dots, x_n$ of n variables,
\item a domain $D(X)= D(x_1)*\dots * D(x_n)$ which is the cartesian product of the domains of the variables in X,
\item a set of constraints $C = \{c_1,\dots,c_e\}$
	\begin{itemize}
	\item a constraint $c(x_1,.., x_k) \in C$ is a relation defined on the variables $x_1,\dots, x_k$
	\item and $Vars(c)$ = $\{x_1,\dots,x_k\}$
	\end{itemize}
\item Binary CSP: only binary constraints
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Definitions}
\textbf{Minimal Domain Consistency}
	\begin{itemize}
	\item A CSP $(X, D(X), C)$ is \textit{minimally domain consistent} iff\\
	 if $\forall x \in X,\quad \#D(x) = 1$ then $(X, D(X), C)$ is satifiable.
	\end{itemize}

\textbf{Global Domain Consistency}
	\begin{itemize}
	\item A CSP $(X, D(X), C)$ is \textit{globally domain consistent} iff \\
	if $\forall x \in X, \forall a \in D(x),$ 
	$\exists{v} \in D(X)_{x=a}:\{ (x_1,v_1), \dots, (x_n, v_n)\} \in Sol(X, D(X), C)$
	\end{itemize}	
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Definitions}
Let $c \in C$ with $x \in Vars(c)$. The set of inconsistent and valid values for x in c wrt $D(X)$ are defined as follows: 
	\begin{itemize}
	\item $Inc(c,x) = \{(x,a)| a \in D(x) \wedge \forall v \in D(Vars(c))_{x=a}: \neg c(v)\}$
	\item $Valid(c,x) = \{(x,a)| a \in D(x) \wedge \forall v \in D(Vars(c))_{x=a}: c(v)\}$
	\end{itemize}
We then define
	\begin{center}
	$Inc(c) = \bigcup_{x \in Vars(c)}Inc(c,x)$
	\end{center}
and similarly for the other set.
\end{frame}
%--------------------------------------------------------------------


%--------------------------------------------------------------------
%                          Domain Consistency
%--------------------------------------------------------------------
\section{Domain Consistency (DC)}
%--------------------------------------------------------------------
\begin{frame}{Domain Consistency}
\textbf{Domain Consistency (DC)} or \textbf{Arc Consistency (AC)}
\begin{itemize}
\item A constraint c is \textit{domain consistent} wrt $D(X)$ iff $Inc(c) = \emptyset$.
\item A CSP $(X, D(X), C)$ is \textit{domain consistent} iff all its constraints are domain consistent wrt $D(X)$.
\end{itemize}
\textbf{Complexity of the most efficient algorithm}
\begin{itemize}
\item AC2001: time complexity is $O(ed^2)$, space complexity is $O(ed)$
\end{itemize}
\end{frame}

%--------------------------------------------------------------------
\begin{frame}{Domain Consistency}
\textbf{Example}
\begin{itemize}
\item If $D(x)= D(y)= \{1,2,3,4,5\}$ and $c(x,y)= x \leq y -2$. 
\item We have $Inc(c,x) = \{(x,4), (x,5)\}, Inc(c,y)= \{(y,1), (y,2)\}, Valid(c)= \emptyset$. 
\item If $D(x)=\{1,2,3\}$ and $D(y)= \{3,4,5\}$, the constraint $c$ is domain consistent.\\
	We have $Valid(c) = \{(x,1), (y,5)\}$.
\end{itemize}
\end{frame}
%--------------------------------------------------------------------



%--------------------------------------------------------------------
%                  Consistency weaker than Domain Consistency
%--------------------------------------------------------------------
\section{Consistencies weaker than DC}
%--------------------------------------------------------------------
\begin{frame}{Consistencies weaker than DC}
\begin{itemize}
\item Forward Checking
\item Bound Consistency
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Forward Checking}
\textbf{Forward Checking (FC)}
\begin{itemize}
\item A constraint $c(x_1,\dots, x_k)$ is \textit{FC consistent} wrt $D(X)$ iff
	\begin{itemize}
%	\item if $\forall x_i \in Vars(c): D(x_i)= \{a_i\}$, then $c(a_1,\dots, a_k)$
	\item if $\exists y \in Vars(c), \forall x \in Vars(c) \setminus \{y\}: \#D(x) = 1$, then $c$ is domain consistent wrt $D(X)$.
	\end{itemize}
\item A CSP $(X, D(X), C)$ is \textit{FC consistent} iff all its constraints are \textit{FC consistent} wrt $D(X)$
\end{itemize}

\textbf{Complexity of the most efficient algorithm}
\begin{itemize}
\item FC: time complexity is $O(ed)$ , space complexity is $O(e)$
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Forward Checking}
\textbf{Example}
\begin{itemize}
\item $3x-2y-z \neq 4$
\item $D(x)= \{1,2,3\}, D(y)=\{1,2\}, D(z)=\{3\}$. The constraint is FC
\item $D(x)= \{1,2,3\}, D(y)=\{\textbf{1}\}, D(z)=\{\textbf{3}\}$. The constraint is not FC\\
Application of FC: $D(x)= \{1,2\}, D(y)=\{1\}, D(z)=\{3\}$
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Bound Consistency}
\textbf{Bound Consistency (BC)}
\begin{itemize}
\item $D^*(X) = D^*(x_1) * \dots D^*(x_n), D^*(x)= [min(D(x)), max(D(x))]$
\item A constraint $c(x_1,\dots, x_k)$ is \textit{bound consistent} wrt $D(X)$ iff $\forall x \in Vars(c)$, we have
	\begin{itemize}
	\item $\forall a \in \{min(D(x)), max(D(x))\}: (x,a) \notin Inc(c,x, D^*(X))$
	\end{itemize}
\item A CSP $(X, D(X), C)$ is \textit{bound consistent} iff all its constraints are \textit{bound consistent} wrt $D(X)$
\end{itemize}

\textbf{Complexity of the most efficient algorithm}
\begin{itemize}
\item BC: time complexity is $O((d^*)^{2})$ , $d^*$ size of the largest domain \cite{handbook:2005}
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Bound Consistency}
\textbf{Example}
\begin{itemize}
\item $D(x)= \{2,3,4\}, D(y)=D(z)=\{2,4\}$
\item $x+y+z=10$ is bound consistent \\
but is not domain consistent ($(x,3)$ has no support)
\end{itemize}
\end{frame}
%--------------------------------------------------------------------




%--------------------------------------------------------------------
%                Consistency stronger than Domain Consistency
%--------------------------------------------------------------------
\section{Consistencies stronger than DC}
\begin{frame}{Consistencies stronger than DC}
\begin{itemize}
\item Triangle-base Local Consistencies
	\begin{itemize}
	\item Restricted Path Consistency (\textbf{RPC})
	\item Path Inverse Consistency (\textbf{PIC})
	\item Max-restricted Path Consistency (\textbf{Max-RPC})
	\end{itemize}
\item Consistency according to the Neighborhood
	\begin{itemize}
	\item Neighborhood Inverse Consistency (\textbf{NIC})
	\end{itemize}
\item Singleton consistencies
	\begin{itemize}
	\item Singleton Arc Consistency (\textbf{SAC})
	\end{itemize}
\item Comparison of Consistencies stronger than DC
\end{itemize}
\end{frame}

%--------------------------------------------------------------------
%--------------------------------------------------------------------
%\subsection{Triangle-base Local Consistencies}
\begin{frame}{Triangle-base Local Consistencies}
	\begin{itemize}
	\item Restricted Path Consistency (\textbf{RPC})
	\item Path Inverse Consistency (\textbf{PIC})
	\item Max-restricted Path Consistency (\textbf{Max-RPC})
	\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Restricted Path Consistency}
\textbf{Restricted Path Consistency (RPC)}

\begin{itemize}
\item A binary CSP $(X,D(X),C)$ is \textit{restricted path consistent} iff it is \textit{domain consistent} and 
$\forall x_i \in X, \forall a \in D(x_i), \forall c_{ij}(x_i, x_j) \in C$ such that $(x_i,a)$ has a unique support $(x_j,b)$ on $c_{ij}(x_i, x_j)$, 

$\forall x_k \in X$ linked to both $x_i, x_j$ by a constraint, there exists $c \in D(x_k)$ such that $c_{ik}(a,c) \wedge c_{jk}(b,c)$
\end{itemize}

\textbf{Complexity of the most efficient algorithm}
\begin{itemize}
\item RPC2: time complexity is $O(en + ed^2 + cd^2)$ , space complexity is $O(ed+cd)$ \cite{domain:2001}

where c is number of the triples of variables $(x_i, x_j, x_k)$ with $c_{ij}, c_{jk}, c_{ki} \in C$
\end{itemize}


\textbf{RPC} is strictly stronger than \textbf{DC} \cite{domain:2001}

\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Restricted Path Consistency}
\textbf{Example}
	\begin{figure}[ht]
		\includegraphics[height=4.6cm]{./images/RPC_DC.png}
		\caption{A CSP on which RPC prunes more than DC: $(x_i , 1)$ is not RPC whereas
		the whole CSP is DC}
	\end{figure}
\end{frame}


%--------------------------------------------------------------------
\begin{frame}{Path Inverse Consistency}
\textbf{Path Inverse Consistency (PIC)}
\begin{itemize}
\item A binary CSP $(X,D(X),C)$ is \textit{path inverse consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall x_j,x_k \in X$ there exists $b \in D(x_j), c \in D(x_k)$ such that $((x_i,a), (x_j,b), (x_k,c))$ is \textit{locally consistent}
\end{itemize}

\textbf{Complexity of the most efficient algorithm}
\begin{itemize}
\item PIC2: time complexity is $O(en + ed^2 + cd^3)$ , space complexity is $O(ed+cd)$ \cite{domain:2001} \cite{handbook:2005}

%\item where c is number of the triples of variables $(x_i, x_j, x_k)$ with $c_{ij}, c_{jk}, c_{ki} \in C$
\end{itemize}


\textbf{PIC} is strictly stronger than \textbf{RPC} \cite{domain:2001}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Path Inverse Consistency}
\textbf{Example}
	\begin{figure}[ht]
		\includegraphics[height=4.6cm]{./images/PIC_RPC.png}
		\caption{A CSP on which PIC prunes more than RPC: $(x_i , 1)$ is not
		PIC whereas the whole network is RPC}
	\end{figure}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Max-restricted Path Consistency}
\textbf{Max-restricted Path Consistency (Max-RPC)}
\begin{itemize}
\item A binary CSP $(X,D(X),C)$ is \textit{max-restricted-path consistent} iff $\forall x_i \in X, \forall a \in D(x_i), \forall c_{ij}(x_i,x_j) \in C$ there exists $b \in D(x_j)$ such that $c_{ij}(a,b)$ 

and $\forall x_k \in X$ there exists $c \in D(x_k)$ with $((x_i,a), (x_j,b), (x_k,c))$ \textit{locally consistent}
\end{itemize}


\textbf{Complexity of the most efficient algorithm}
\begin{itemize}
\item Max-RPC1: time complexity is $O(en + ed^2 + cd^3)$ , space complexity is $O(ed+cd)$ \cite{domain:2001}
\end{itemize}

\textbf{Max-RPC} is strictly stronger than \textbf{PIC} \cite{domain:2001}

\begin{itemize}
\item \textbf{Max-RPC $\longrightarrow$ PIC $\longrightarrow$ RPC}
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Max-restricted Path Consistency}
\textbf{Example}
	\begin{figure}[ht]
		\includegraphics[height=4.8cm]{./images/MaxRPC_PIC.png}
		\caption{A CSP on which Max-RPC prunes more than PIC: $(x_i , 1)$ is not Max-RPC
		whereas the whole CSP is PIC}
	\end{figure}
\end{frame}

%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}{\Large{Consistency according to the Neighborhood}}
\textbf{Neighborhood Inverse Consistency (NIC)}
\begin{itemize}
\item A binary CSP $(X,D(X),C)$ is \textit{neighborhood inverse consistent} iff $\forall x_i \in X, \forall a \in D(x_i)$, the instantiation $(x_i, a)$ can be extended to a {\huge\textbf{insert definition}} locally consistent instantiation on the set of all variables involved in a constraint with $x_i$
\end{itemize}


\textbf{Complexity of the most efficient algorithm}
\begin{itemize}
\item NIC1: time complexity is $O(g^2(n + ed)d^{g+1})$ , space complexity is $O(n)$, where $g$ is the maximum degree of a variable in the associated hypergraph \cite{domain:2001} \cite{handbook:2005}
\end{itemize}

\textbf{NIC} is strictly stronger than \textbf{Max-RPC} \cite{domain:2001}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Neighborhood Inverse Consistency (NIC)}
\textbf{Example}
	\begin{figure}[ht]
		\includegraphics[height=5cm]{./images/NIC_Max-RPC_img.png}
		\caption{A CSP on which NIC prunes more than Max-RPC: $(x_i , 1)$ is not NIC whereas the whole CSP is Max-RPC}
	\end{figure}
\end{frame}

%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}{Singleton consistencies}
\textbf{Singleton Arc Consistency (SAC)}
\begin{itemize}
\item A binary CSP $(X,D(X),C)$ is \textit{singleton arc consistent} iff $\forall x_i \in X, \forall a \in D(x_i)$, the subproblem $(X, D(X)_{x_i = a}, C)$ is \textit{domain consistent}
\end{itemize}


\textbf{Complexity of the most efficient algorithm}
\begin{itemize}
\item SAC1: time complexity is $O(en^2d^4)$ , space complexity is $O(ed)$ \cite{domain:2001}
\end{itemize}


\textbf{SAC} is strictly stronger than \textbf{Max-RPC}

but \textbf{SAC} and \textbf{NIC} are in comparable \cite{domain:2001}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}{Singleton consistencies}
\textbf{Example}
	\begin{figure}[ht]
		\includegraphics[height=4.8cm]{./images/SAC_MaxRPC.png}
		\caption{ A CSP on which SAC prunes more than Max-RPC:
		$(x_i , 2)$ is not SAC whereas the whole network is Max-RPC}
	\end{figure}
\end{frame}

%--------------------------------------------------------------------
%--------------------------------------------------------------------
\begin{frame}{Comparison}
From \cite{domain:2001}, \cite{handbook:2005}
	\begin{center}
	  \begin{figure}[ht]
		\includegraphics[height=2.8cm]{./images/comparison_consistency2.png}
		\caption{Summary of the comparison between domain-based consistencies.
		
		 A $\rightarrow$ B means that local consistency A is strictly stronger than local consistency B. (The stronger relation is transitive.)}
	  \end{figure}
	\end{center}

We can find the complete proofs of the shema in \cite{domain:2001}.
\end{frame}
%--------------------------------------------------------------------
%\section{Conclusion}
%\begin{frame}{Conclusion}
%\end{frame}
%--------------------------------------------------------------------
\section*{Références}
\begin{frame}
\begin{thebibliography}{9}
\frametitle{References}
\bibitem{materiel} Documents in the course
\bibitem{domain:2001} Debruyne, Romuald, and Christian Bessiére. "Domain filtering consistencies." J. Artif. Intell. Res. (JAIR) 14 (2001): 205-230.
\bibitem{handbook:2005} Bessiere, Christian. "Constraint propagation." Handbook of constraint programming (2006): 29-83.
%--------------------------------------------------------------------
\end{thebibliography}
\end{frame}
%--------------------------------------------------------------------
\section*{}
\begin{frame}
\begin{center}
\huge Thank you!
\end{center}

\end{frame}
\end{document}